package sort.mergesort;

import sort.quiksort.QuikSort;
import sort.util.RamdomUtil;

/**
 * 归并排序
 */
public class MergeSort {

    private static int[] temp;

    public static void merge(int[] a, int low, int mid, int high) {
        int i = low, k, j = mid + 1;
        for (int x = low; x <= high; x++) {
            temp[x] = a[x];
        }

        for (k = low; k <= high; k++) {
            if (i > mid) a[k] = temp[j++];
            else if (j > high) a[k] = temp[i++];
            else if (temp[i] > temp[j]) a[k] = temp[j++];
            else a[k] = temp[i++];
        }

    }

    public static void sort(int[] a, int low, int high) {
        int mid = low + (high - low) / 2;
        if ((high - low) == 0) return;
        sort(a, low, mid);
        sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }

    public static void sort(int[] a) {
        temp = new int[a.length];
        sort(a, 0, a.length - 1);
    }

    public static void main(String[] args) {
        for (int inc = 1000; inc <= 20000; inc += 5000) {
            int[] test2 = RamdomUtil.generateRandomArray(inc);
            for (int i = 0; i < 4; i++) {
                System.out.print(test2[i] + " ");
            }
            System.out.println();
            int[] test1 = new int[inc];
            System.arraycopy(test2, 0, test1, 0, inc);
            for (int i = 0; i < 4; i++) {
                System.out.print(test1[i] + " ");
            }
            System.out.println();
            MergeSort.sort(test2);
            QuikSort.sort(test1);
            for (int i = 0; i < 4; i++) {
                System.out.print(test2[i] + " ");
            }
            System.out.println();
            for (int i = 0; i < 4; i++) {
                System.out.print(test1[i] + " ");
            }
            System.out.println();
        }

//        int[] test2=new int[]{29,24,92,17};
//        System.out.println("排序前");
//        for(int x:test2){
//            System.out.print(x+" ");
//        }
//        StopWatch first = new StopWatch("First");
//        first.start("A");
//        sort(test2);
//        first.stop();
//        System.out.println(first.prettyPrint());
//        merge(test,0,2,5);
//        System.out.println("排序后");
//        for(int x:test2){
//            System.out.print(x+" ");
//        }
//        System.out.println();
    }
}
